package skiplist;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

public class SkipListImpl<E extends Comparable<? super E>>
		implements
			SkipList<E> {

	private final int levels;

	private final ListElement anchor = new ListElement(null);

	private final Class<E> elementClass;

	/**
	 * Creates a new skip list using the specified maximum level.
	 * 
	 * @param maxLevel
	 *            The maximum level allowed for elements of this skip list
	 * @param elementClass
	 *            The class of elements to store in this skip list
	 */
	public SkipListImpl(final int maxLevel, final Class<E> elementClass) {
		this.levels = maxLevel;
		this.elementClass = elementClass;
	}

	@Override
	public boolean add(final E elementToAdd) {
		int nodeLevel = 1;
		final Random r = new Random();
		while (r.nextBoolean() && nodeLevel < this.levels) {
			nodeLevel++;
		}

		return this.add(elementToAdd, nodeLevel);
	}

	@Override
	public boolean add(final E elementToAdd, final int nodeLevel) {
		if (nodeLevel > this.levels) {
			throw new IllegalArgumentException("Level " + nodeLevel
					+ " exceeds the maximum level for this skip list");
		}

		final List<ListElement> previousElements = new ArrayList<ListElement>(
				this.levels);
		if (this.findPreviousElements(elementToAdd, previousElements)) {
			return false;
		}

		ListElement newElement = new ListElement(elementToAdd);
		for (int level = 1; level <= nodeLevel; level++) {
			newElement.setLink(level, previousElements.get(level - 1).getLink(
					level));
			previousElements.get(level - 1).setLink(level, newElement);
		}

		return true;
	}

	@Override
	public boolean addAll(Collection<? extends E> c) {
		boolean skiplistChanged = false;
		for (E e : c) {
			skiplistChanged |= this.add(e);
		}
		return skiplistChanged;
	}

	@Override
	public void clear() {
		this.anchor.clear();
	}

	@Override
	public boolean contains(final Object lookFor) {
		return this.findElement(elementClass.cast(lookFor)) != null;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		boolean containsAll = true;
		for (Object o : c) {
			containsAll &= this.contains(o);
		}
		return containsAll;
	}

	public E first() {
		return this.anchor.getLink(1) != null ? this.anchor.getLink(1)
				.getElement() : null;
	}

	@Override
	public boolean isEmpty() {
		return this.anchor.getLink(1) == null;
	}

	@Override
	public Iterator<E> iterator() {
		return new SkipListIterator();
	}
	@Override
	public boolean remove(final Object elementToRemove) {
		final List<ListElement> previousElements = new ArrayList<ListElement>(
				this.levels);
		if (!this.findPreviousElements(this.elementClass.cast(elementToRemove),
				previousElements)) {
			return false;
		}

		final int elementToRemoveLevel = this.findElement(
				this.elementClass.cast(elementToRemove)).getLevel();
		for (int level = 1; level <= elementToRemoveLevel; level++) {
			previousElements.get(level - 1).setLink(
					level,
					previousElements.get(level - 1).getLink(level).getLink(
							level));
		}
		return true;
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		boolean skiplistChanged = false;
		for (Object o : c) {
			skiplistChanged |= this.remove(o);
		}
		return skiplistChanged;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		throw new UnsupportedOperationException();
	}

	@Override
	public int size() {
		ListElement element = this.anchor;
		int i = 0;
		while (element.getLink(1) != null) {
			i++;
			element = element.getLink(1);
		}
		return i;
	}

	@Override
	public Object[] toArray() {
		Object[] result = new Object[this.size()];
		final Iterator<E> it = this.iterator();
		for (int i = 0; i < this.size(); i++) {
			result[i] = it.next();
		}
		return result;
	}

	@Override
	public <T> T[] toArray(T[] a) {
		throw new UnsupportedOperationException();
	}

	@Override
	public String toString() {
		ListElement curElement = this.anchor;
		final List<StringBuilder> result = new ArrayList<StringBuilder>(
				this.anchor.getLevel());
		for (int level = 1; level <= this.anchor.getLevel(); level++) {
			result.add(new StringBuilder());
		}
		while (curElement != null) {
			result.get(0).append(curElement);
			result.get(0).append('-');
			for (int level = 2; level <= this.anchor.getLevel(); level++) {
				for (int i = 0; i < curElement.toString().length(); i++) {
					if (i == curElement.toString().length() / 2
							&& curElement.getLevel() >= level) {
						result.get(level - 1).append('+');
					} else if (curElement != this.anchor
							|| i > curElement.toString().length() / 2) {
						result.get(level - 1).append('-');
					} else {
						result.get(level - 1).append(' ');
					}
				}
				result.get(level - 1).append('-');
			}

			curElement = curElement.getLink(1);
		}

		final StringBuilder totalResult = new StringBuilder();
		for (int level = 1; level <= this.anchor.getLevel(); level++) {
			totalResult.append(result.get(level - 1)).append('|').append('\n');
		}

		return totalResult.toString();
	}

	/**
	 * Finds an element in the element list and returns it.
	 * 
	 * @param keyToFind
	 *            The key for which the element is requested
	 * @return The element found or <code>null</code> if no element with the
	 *         requested key exists
	 */
	private ListElement findElement(final E keyToFind) {
		ListElement element = this.anchor;
		for (int level = this.levels; level > 0; level--) {
			while (element.getLink(level) != null
					&& element.getLink(level).getElement().compareTo(keyToFind) < 0) {
				element = element.getLink(level);
			}
		}
		if (element.getLink(1) == null
				|| !element.getLink(1).getElement().equals(keyToFind)) {
			return null;
		} else {
			return element.getLink(1);
		}
	}

	/**
	 * Detects the previous elements compared to a key considering all levels.
	 * 
	 * @param keyToFind
	 *            The key for which the previous elements are requested assumed
	 *            an element with that key would exist
	 * @param previousElements
	 *            The list where to save the resulting previous elements ordered
	 *            by level
	 * @return <code>true</code> if an element with the key to find exists yet,
	 *         <code>false</code> otherwise
	 */
	private boolean findPreviousElements(final E keyToFind,
			final List<ListElement> previousElements) {
		ListElement element = this.anchor;
		for (int level = this.levels; level > 0; level--) {
			while (element.getLink(level) != null
					&& element.getLink(level).getElement().compareTo(keyToFind) < 0) {
				element = element.getLink(level);
			}
			previousElements.add(element);
		}
		Collections.reverse(previousElements);
		if (element.getLink(1) != null
				&& element.getLink(1).getElement().equals(keyToFind)) {
			return true;
		}
		return false;
	}

	private class ListElement {
		private final E element;
		private final List<ListElement> links;

		ListElement(final E element) {
			this.element = element;
			this.links = new ArrayList<ListElement>(SkipListImpl.this.levels);
			this.setLink(1, null);
		}

		@Override
		public String toString() {
			return "[" + this.element + "]";
		}

		void clear() {
			this.links.clear();
			this.setLink(1, null);
		}

		E getElement() {
			return element;
		}

		int getLevel() {
			return this.links.size();
		}

		ListElement getLink(final int level) {
			if (this.links.size() >= level) {
				return this.links.get(level - 1);
			} else {
				return null;
			}
		}

		void setLink(final int level, final ListElement element) {
			while (this.links.size() < level) {
				this.links.add(null);
			}
			this.links.set(level - 1, element);
		}

	}

	private class SkipListIterator implements Iterator<E> {

		private SkipListImpl<E>.ListElement current = SkipListImpl.this.anchor;

		@Override
		public boolean hasNext() {
			return this.current.getLink(1) != null;
		}

		@Override
		public E next() {
			if (this.hasNext()) {
				this.current = this.current.getLink(1);
				return this.current.getElement();
			} else {
				return null;
			}
		}

		@Override
		public void remove() {
			SkipListImpl.this.remove(this.current.getElement());
		}

	}

}
